package algorithm.sort;


public class MergeBUSort implements Sort {
    @Override
    public String name() {
        return "归并排序自底向上";
    }

    @Override
    public void sort(Integer[] arr) {
        for (int size = 1; size <= arr.length; size *= 2) {
            for (int i = 0; i + size < arr.length; i += 2 * size) {
                int start = i;
                int middle = i + size - 1;
                int end = Math.min(i + 2 * size - 1, arr.length - 1);
                merge(arr, start, middle, end);
            }
        }
    }


    private void merge(Integer[] arr, int start, int middle, int end) {
        int length = end - start+1;
        Integer[] copyArray = new Integer[length];
        System.arraycopy(arr, start, copyArray, 0, length);
        int l = start;
        int r = middle+1;
        for (int index = start; index <=end ; index++) {

            if (l>middle){
                //左边处理完
                arr[index]=copyArray[r-start];
                r++;
            }else if (r>end){
                //右边处理完
                arr[index]=copyArray[l-start];
                l++;
            }else if (copyArray[l-start]>copyArray[r-start]){
                arr[index]=copyArray[r-start];
                r++;
            }else{
                arr[index]=copyArray[l-start];
                l++;
            }
        }
    }


}
